package com.mlh.dp.编辑距离;

/**
 * @author 缪林辉
 * @date 2024/5/23 10:28
 * @DESCRIPTION
 */
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。
public class 不同的子序列 {
    public int method1(String s, String t) {
        //dp数组定义
        // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
        int sLen=s.length();
        int tLen=t.length();
        int[][]dp=new int[sLen+1][tLen+1];
        //初始化
        // 每次当初始化的时候，都要回顾一下dp[i][j]的定义，不要凭感觉初始化。
        // dp[i][0]表示什么呢？
        // dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
        // 那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
        // 再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
        // 那么dp[0][j]一定都是0，s如论如何也变成不了t。
        // 最后就要看一个特殊位置了，即：dp[0][0] 应该是多少。
        // dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
        for (int i = 0; i <=sLen; i++) {
            dp[i][0]=1;
        }
        //这里t在外层 s在内层主要是为了省略掉 遍历t以j-1结尾的字符串长度 大于 s以i-1结尾的字符串长度 此时s的子序列绝不可能包含t
        for (int j = 1; j <=tLen; j++) {
            for (int i = j; i <=sLen ; i++) {
                if(s.charAt(i -1)==t.charAt(j -1)){
                    dp[i][j]=dp[i -1][j]+dp[i -1][j -1];
                }else{
                    dp[i][j]=dp[i -1][j];
                }
            }
        }
        return dp[sLen][tLen];
    }
}
